Матч 306, Подсчет путей (TourCounting)

Дивизион 1, Уровень 3

В ориентированном графе g следует найти количество разных циклов длины, меньшей k. Результат следует вернуть по модулю m. Циклом называется непустая последовательность вершин, последовательно соединенных ребрами, причем между последней вершиной и первой существует ребро. Два цикла считаются разными, если их последовательности не идентичны.

Ячейка g[i][j] равна ‘Y’, если существует ребро, соединяющее i -ое ребро с j -ым. Иначе g[i][j] равно ‘N’.

Класс: TourCounting

Метод: int countTours(vector<string> g, int k, int m)

Ограничения: g содержит от 1 до 35 строк одинаковой длины, состоящих из букв ‘Y’ и ‘N’, 1 £ k £ 10⁶, 1 £ m £ 10⁹.

Вход. Массив строк g, описывающий матрицу смежности графа, целые числа k и m.

Выход. Количество разных циклов длины, меньшей k. Результат вернуть по модулю m.

Пример входа

g	k	m
{"NYNY", "NNYN", "YNNN", "YNNN"}	6	100
{"NYNNNNN", "NNYNNNN", "NNNYNNN", "NNNNYNN", "NNNNNYN", "NNNNNNY", "YNNNNNN"}	40	13
{"NYNY", "NNNN", "YYNY", "NYNN"}	1000000	1000000000

Пример выхода

12

9

0

РЕШЕНИЕ

алгебра + графы

Теорема. Пусть А – матрица смежности графа. Тогда A^k[i][j] содержит количество путей, ведущих из i -ой вершины в j -ую, и имеющих длину k. Число циклов, имеющих длину k, равно сумме диагональных элементов матрицы A^k.

Определение. Следом матрицы называется сумма ее диагонльных элементов.

Количество разных циклов длины, меньшей k, равно сумме диагональных элементов матрицы S = A + A² + A³ + … + A^k-1. Возведение в степень A^k можно совершить за O(log k). Рассмотрим алгоритм вычисления матрицы S за время O(log k).

Пусть функция sum(k) вычисляет значение суммы A + A² + … + A^k, а pow(k) находит A^k.

Если k четное, то

sum(k) = A + A² + … + A^k = A + A² + … + A^k/2 + A^k/2+1 + … + A^k =

= (A + A² + … + A^k/2) + A^k/2 * (A + A² + … + A^k/2) =

= sum(k / 2) * pow(k / 2) + sum(k / 2)

Если k нечетное, то

sum(k) = A + A² + … + A^k =

(A + A² + … + A^{k – 1}) * A + A = sum(k – 1) * A + A

Ответом на поставленную задачу будет значение следа матрицы sum(k – 1).

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

using namespace std;

typedef vector<int> vi;

typedef vector<vector<int> > vvi;

vvi add(vvi a,vvi b, int mod)

{

int i, j, n = a.size();

vvi c(n, vi(n));

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

c[i][j] = (a[i][j] + b[i][j]) % mod;

return c;

}

vvi mult(vvi a,vvi b, int mod)

{

int i, j, k, s, n = a.size();

vvi c(n, vi(n));

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

{

for(s = k = 0; k < n; k++) s = (s + (long long)a[i][k] * b[k][j]) % mod;

c[i][j] = s;

}

return c;

}

vvi pow(vvi a, int k, int mod)

{

int i, n = a.size();

vvi res(n, vi(n, 0));

for(i = 0; i < n; i++) res[i][i] = 1;

while (k > 0)

{

if (k % 2) res = mult(res, a, mod);

a = mult(a, a, mod);

k /= 2;

}

return res;

}

vvi sum(vvi a, int k, int mod)

{

if (k == 1) return a;

if (k % 2)

{

vvi temp = sum(a,k-1,mod);

return add(mult(temp,a,mod),a,mod);

}

vvi temp = sum(a,k/2,mod);

vvi powk_2 = pow(a,k/2,mod);

return add(mult(temp,powk_2,mod),temp,mod);

}

class TourCounting

{

public:

int countTours(vector<string> g, int k, int m)

{

int i, j, n = g.size();

vvi mas(n, vi(n, 0));

long long res;

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

if (g[i][j] == 'Y') mas[i][j] = 1; else mas[i][j] = 0;

res = 0;

vvi temp = sum(mas,k-1,m);

for(i = 0; i < n; i++)

res = (res + temp[i][i]) % m;

return res;

}

};